class Solution(object):
    def smallestGoodBase(self, n):
        """
        :type n: str
        :rtype: str
        """
        n = int(n)
        min_val = n - 1
        t = 2
        x = int(n ** (1 / t))

        def cal(x, t):
            num = 0
            for i in range(t + 1):
                num += x ** i
            return num

        while x >= 2:
            num = cal(x, t)
            while num > n:
                x = x - 1
                num = cal(x, t)
            if num == n:
                min_val = x
            t += 1
            x = int(n ** (1 / t))

        return str(min_val)


data = Solution()
n = "1000000000000000000"
print(data.smallestGoodBase(n))
